package com.arron.algorithm.leetcodetop100.单调栈;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * 题解
 * https://leetcode.cn/problems/remove-duplicate-letters/solutions/417758/you-qian-ru-shen-dan-diao-zhan-si-lu-qu-chu-zhong-/
 * https://leetcode.cn/problems/remove-duplicate-letters/solutions/290200/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/
 */
public class 去除重复字母 {

    Stack<Character> stack = new Stack<>();

    //输入：s = "bcabc"
    //输出："abc"
    public String removeDuplicateLetters(String s) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

        int[] count = new int[26];
        // 标记字母是否已经被入栈
        boolean[] flag = new boolean[26];
        char[] chars = s.toCharArray();
        // 统计所有字母出现的次数
        for (int i = 0; i < chars.length; i++) {
            count[chars[i] - 'a'] += 1;
        }


        for (int i = 0; i < chars.length; i++) {

            count[chars[i] - 'a']--;
            if (flag[chars[i] - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > chars[i]) {
                if (count[stack.peek() - 'a'] == 0) {
                    break;
                }
                flag[stack.pop() - 'a'] = false;
            }
            stack.push(chars[i]);
            flag[chars[i] - 'a'] = true;
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {

        去除重复字母 letter = new 去除重复字母();

        String s = "abacb";

        System.out.println(letter.removeDuplicateLetters(s));

    }


}
